//
//  IsBalanced.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/8/18.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  110. 平衡二叉树

import UIKit

//110. 平衡二叉树
/*
 给定一个二叉树，判断它是否是高度平衡的二叉树。

 本题中，一棵高度平衡二叉树定义为：

 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

 示例 1:

 给定二叉树 [3,9,20,null,null,15,7]

     3
    / \
   9  20
     /  \
    15   7
 返回 true 。

 示例 2:

 给定二叉树 [1,2,2,3,3,null,null,4,4]

        1
       / \
      2   2
     / \
    3   3
   / \
  4   4
 返回 false 。
 */


class IsBalanced: NSObject {
    //自顶向下的递归 耗时72ms  时间复杂度0(n²)  n是二叉树的节点个数
    func isBalanced(_ root: TreeNode?) -> Bool {
        
        guard root != nil else {
            return true
        }
        
        let leftNum = self.deepTreeNum(root?.left)
        let rightNum = self.deepTreeNum(root?.right)
        
        let diff = abs(leftNum - rightNum)
        
        if diff <= 1 {
            return self.isBalanced(root?.left) && self.isBalanced(root?.right)
            
        }else {
            return false
        }
    }
    
    func deepTreeNum(_ node: TreeNode?) -> Int{
        guard node != nil else {
            return 0
        }
        return max(deepTreeNum(node?.left), deepTreeNum(node?.right)) + 1
    }
    
    
    //自底向上的递归 耗时52ms  时间复杂度0(n)  n是二叉树的节点个数
    //思路是对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。
    func isBalanced2(_ root: TreeNode?) -> Bool {
        
        return self.helper(root) >= 0
    }
    
    func helper(_ root: TreeNode?) -> Int{
        guard root != nil else {
            return 0
        }
        
        let left = self.helper(root!.left)
        let right = self.helper(root!.right)
        if left == -1 || right == -1 || abs(left - right) > 1 {
            return -1
        }else{
            return max(left, right) + 1
        }
    }
}
